package arithmetic2;

/**
 * @author macpro
 * @date 2019-08-04
 * @function
 *  求最大成水量
 */
public class T_011_MaxAreaForContainerWater {
    public static void main(String[] args) {
//        System.out.println(maxArea(new int[]{1,8,6,2,5,4,8,3,7}));
        System.out.println(maxAreaDoublePoint(new int[]{1,8,6,2,5,4,8,3,7}));
    }


    public static int maxArea(int[] height) {
        if (height == null || height.length<2){
            return 0;
        }
        // 1 求乘机最大值，边界，>0 ,数组不会超过int ，乘 超过int
        // 2 possible solution， 当前值的最大值  1-i value
        //      暴力法，1-n  时间复杂度on2  空间 o1 复杂度，每一个都求解，右边最大值，左边最大值

        long res =0;
        for (int r = 1; r < height.length; r++) {
            for (int l = 0; l < r; l++) {
                int min = Math.min(height[l], height[r]);
                long temp = min  *(r-l);
                if (temp>res){
                    res = temp;
//                    System.out.println("left "+l + " right "+ r +" min"+min);
                }
            }

        }

        if (res >Integer.MAX_VALUE){
            System.out.println("res bigger than int max value");
        }
        return (int) res;

    }


    //todo Offical two Point

    /**
     * 思路
     * 1 双指针 首尾各1端
     * 2 计算2端之间的area
     * 3 移动，矮的一端，向长的一端，移动，（todo 两端，都是最小值移动，所以不会漏掉 大的区域计算）
     * 4 时间复杂度 On   空间复杂度O1
     *
     * 还是有些疑问，如果l r相等，如何移动？？？
     * 如果下一个值，小，那么没有关系
     * 如果下一个值，大，那么会移动另一边。。over
     *
     * 证明：
     * https://leetcode-cn.com/problems/container-with-most-water/solution/shuang-zhi-zhen-fa-zheng-que-xing-zheng-ming-by-r3/
     * @param height
     * @return
     */
    public static int maxAreaDoublePoint(int[] height) {
        if (height == null || height.length<2){
            return 0;
        }
        // 1 求乘机最大值，边界，>0 ,数组不会超过int ，乘 超过int
        // 2 possible solution， 当前值的最大值  1-i value
        //      暴力法，1-n  时间复杂度on2  空间 o1 复杂度，每一个都求解，右边最大值，左边最大值

        long res =0;
        int r = height.length-1;
        int l = 0;
        while (l<r){
            int rValue = height[r];
            int lValue = height[l];
            int minHeight = Math.min(rValue, lValue);
            long tempArea = minHeight *(r-l);
            if (tempArea>res){
//                System.out.println("left "+l + " right "+ r +" min"+tempArea);
                res = tempArea;
            }

            if (rValue>lValue){
                l++;
            }else {
                r--;
            }
        }

        if (res >Integer.MAX_VALUE){
            System.out.println("res bigger than int max value");
        }
        return (int) res;
    }
}
